#include "linearList.h"

//顺序表打印
void sequenceList::print()
{
    std::cout << curNumberOfItem << ":";

    for(int i = 0; i < curNumberOfItem-1; i++)
    {
        std::cout << myList[i] << ",";
    } 

    std::cout << myList[curNumberOfItem-1] << std::endl;
};
//顺序表创建
sequenceList::sequenceList(const int& volume, const int& length, float array[]):
maxCapcity(volume), curNumberOfItem(length){
    this -> myList = new float[volume];//分配动态内存储存
    for(int i = 0; i < length; i ++){
        this -> myList[i] = array[i];
    }
};
//顺序表析构函数
sequenceList::~sequenceList(){
    delete[] myList;
    curNumberOfItem = 0;
};
//顺序表直接插入
bool sequenceList::addItem(const float& item){
    if(curNumberOfItem >= maxCapcity) //检查是否超出最大限度
        return false;
    else    
        myList[curNumberOfItem] = item;
    curNumberOfItem ++;
    return true;
};
//顺序表选择位置插入
bool sequenceList::insertItem(const int& index,const float& item){
    if(curNumberOfItem >= maxCapcity)
        return false;
    else if(index < 0 || index > curNumberOfItem)
        return false;//检查插入位置是否合法
    else 
        curNumberOfItem ++;
        for(int i = curNumberOfItem - 1; i > index; i --){
            myList[i] = myList[i - 1];
        }
        myList[index] = item;
    return true;
};
//顺序表删除元素
int sequenceList::deleteItem(const float& item){
    int i = 0;
    for(i = 0; i < curNumberOfItem; i ++){
        if(myList[i] == item){
            for(int u = i; u < curNumberOfItem; u ++){
                myList[u] = myList[u + 1];
            }
            curNumberOfItem --;
            return i;
            break;
        }            
    }
    return -1;
};
//顺序表序号查找
bool sequenceList::locate(const int& index, float& val){
    if(index < 0 || index >= curNumberOfItem)
        return false;
    else
        val = myList[index];//值存入val中
        return true;
};
//顺序表按值查找
int sequenceList::locate(const float& item){
    int i = 0;
    for(i = 0; i < curNumberOfItem; i ++){
        if(myList[i] == item)
            return i;
    }
    return -1;
};
//顺序表反转
void sequenceList::reverse(){
    for(int i = 0; i < (curNumberOfItem) / 2; i++){
        float t = 0.0;
        t = myList[i];
        myList[i] = myList[curNumberOfItem - 1 - i];
        myList[curNumberOfItem - 1 - i] = t;
    }
};

//节点建立
listNode::listNode(float nodeData, listNode* succ){
    data = nodeData;
    next = NULL;
}
listNode::~listNode() = default;
//链表创建
linkList::linkList(){
        listSize = 0;
        firstNode = (listNode*)malloc(sizeof(listNode));
        lastNode = (listNode*)malloc(sizeof(listNode));
        curNode = (listNode*)malloc(sizeof(listNode));
    };
linkList::linkList(const int& length, float array[]){
    listSize = length;
    lastNode = (listNode*)malloc(sizeof(listNode));
    firstNode = (listNode*)malloc(sizeof(listNode));
    curNode = (listNode*)malloc(sizeof(listNode));
    curNode -> next = NULL;
    lastNode -> next = NULL;
    firstNode = lastNode;
    for(int i = 0; i < length; i ++){
        listNode* newNode = (listNode*)malloc(sizeof(listNode));
        newNode -> data = array[i];
        newNode -> next = NULL;
        if(i == 0)
            firstNode -> next = newNode;
        curNode -> next = newNode;
        curNode = newNode;
        if(i == length - 1)
            lastNode = newNode;
    }
    curNode = firstNode;
};
//链表析构
linkList::~linkList(){
    while(firstNode -> next != NULL){
        auto node = firstNode -> next;
        firstNode -> next = node -> next;
        free(node);
        node = NULL;
    }
    curNode = lastNode;
    firstNode = lastNode;
    listSize = 0;
};
//链表头部插入
bool linkList::headInsertItem(const float& item){
    listNode* newNode = (listNode*)malloc(sizeof(listNode));
    newNode -> data = item;
    newNode -> next = NULL;
    if (newNode == nullptr) return false;
    newNode -> next = firstNode -> next; 
    firstNode -> next = newNode;
    listSize ++;
    return true;
};          //按值头插
bool linkList::tailInsertItem(const float& item){
    listNode* newNode = (listNode*)malloc(sizeof(listNode));
    newNode -> data = item;
    newNode -> next = NULL;
    if (newNode == nullptr) return false;
    lastNode -> next = newNode;
    lastNode = newNode;
    if (firstNode->next == nullptr) 
        firstNode->next = newNode;
    listSize ++;
    return true;
};          //按值尾插
//插入特定位置
int linkList::insertItem(const int& index,const float& item){
    if(index < 0 || index > listSize)
        return -1;
    listNode* newNode = (listNode*)malloc(sizeof(listNode));
    newNode -> next = NULL;
    newNode -> data = item;
    curNode = firstNode;
    int i = 0;
    while(i != index){
        curNode = curNode -> next;
        i ++;
    }
    newNode -> next = curNode -> next;
    curNode -> next = newNode;
    curNode = firstNode;
    listSize ++;
    return index;
};   
//删除特定元素
int linkList::deleteItem(const float& item){
    curNode = firstNode;
    if(listSize == 0)
        return -1;
    for(int i = 0; i < listSize; i ++){
        if(curNode -> next -> data == item){
            auto newNode = curNode -> next;
            curNode -> next = curNode -> next -> next;
            free(newNode);
            curNode = firstNode;
            listSize --;
            return i;
        }
        curNode = curNode -> next; 
    }
    return -1;
};               
//按序号查找
bool linkList::locate(const int& index, float& val){
    if(index < 0 || index >= listSize)//检查序号是否合法
        return false;
    curNode = firstNode -> next;
    int i = 0;
    while(i != index){
        curNode = curNode -> next;
        i ++;
    }
    val = curNode -> data;
    return true;
}; 
//按值查找           
int linkList::locate(const float& item){
    if(listSize == 0)
        return -1;
    curNode = firstNode -> next;
    int i = 0;
    while ((curNode != NULL))
    {
        if(item == curNode -> data){
            return i;
        }
        curNode = curNode -> next;
        i ++;
    }
    return -1;
};             
//升序排列
void linkList::ascendingOrder(){
    float com = 0;
    curNode = firstNode -> next;
    float* array = new float[listSize];
    for(int i = 0; i < listSize; i ++){ //将数据存入动态内存中
        com = curNode -> data;
        array[i] = com;
        for(int j = 0; j < i; j ++){ //冒泡排序
            if(com < array[j]){
                float y = 0;
                y = array[j];
                array[j] = com;
                array[i] = y;
                com = y;
            }
        }
        curNode = curNode -> next;
    }
    curNode = firstNode -> next;
    for(int i = 0; i < listSize; i ++){
        curNode -> data = array[i];
        curNode = curNode -> next;
    }
    delete [] array;
    };  
//链表反转                    
void linkList::reverse(){
    curNode = firstNode;
    auto p1 = curNode;
    auto p2 = firstNode;
    for(int i = 0; i < listSize - 1; i ++){
        p2 = firstNode;
        for(int j = 0; j < listSize; j ++){
            p1 = curNode;
            curNode = curNode -> next;
        }
        for(int o = 0; o < i; o ++){
            p2 = p2 -> next;
        }
        curNode -> next = p2 -> next;
        p2 -> next = curNode;
        p1 -> next = NULL;
        lastNode = p1;
        curNode = firstNode;
    }
};                     
//链表打印
void linkList::print()
{
    curNode = firstNode;

    std::cout << listSize << ":";

    while(curNode != lastNode)
    {
        if(curNode->next == lastNode)
            std::cout << curNode->next->data << std::endl;
        else
        {
            std::cout << curNode->next->data << ",";
        }
        
        
        curNode = curNode->next;
    }
}
int linkList::length(){
    return listSize;
}
listNode* linkList::first(){
    return firstNode;
}
listNode* linkList::last(){
    
    return lastNode;
}
//链表降序排列
void linkList::decreaseOrder(){
    float com = 0;
    curNode = firstNode -> next;
    float* array = new float[listSize];
    for(int i = 0; i < listSize; i ++){
        com = curNode -> data;
        array[i] = com;
        for(int j = 0; j < i; j ++){
            if(com > array[j]){
                float y = 0;
                y = array[j];
                array[j] = com;
                array[i] = y;
                com = y;
            }
        }
        curNode = curNode -> next;
    }
    curNode = firstNode -> next;
    for(int i = 0; i < listSize; i ++){
        curNode -> data = array[i];
        curNode = curNode -> next;
    }
    delete [] array;
    };
//返回链表数据到动态内存
float* linkList::array(){
    curNode = firstNode -> next;
    float* array = new float[listSize];
    for (int i = 0; i < listSize; i++)
    {
        array[i] = curNode -> data;
        curNode = curNode -> next;
    }
    return array;
}            
//合并链表
void merge(linkList& list1, linkList& list2){
    int l = 0;
    l = list1.length() + list2.length();//用函数访问private元素
    float* a1 = list1.array();
    float* a2 = list2.array();
    for(int i = 0; i < list2.length(); i ++){
        list1.headInsertItem(a2[i]);
    }
    list1.decreaseOrder();
};